package tree;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author : Rookie
 * @description : 二叉搜素树中的众数
 * @date : 2023/10/28
 */
public class BinarySearchTreeMode {

    public static void main(String[] args) {
        int[] tree = new int[] {8,5,10,5,7,-1,15};
        TreeNode root = BinaryTreeUtil.buildTree(tree);
//        List<Integer> result = getMode(root);
        List<Integer> result = new ArrayList<>();
        getMode(null, root, 0, 0, result);
        System.out.printf("众数有%d个，分别是%s：", result.size(),result);
    }

    /**
     * 普通解法
     * @param root
     * @return
     */
    private static List<Integer> getMode(TreeNode root) {
        Map<Integer, Integer> countMap = getCountMap(root, new HashMap<>());
        Integer num = countMap.values()
                .stream()
                .reduce(Integer::max)
                .orElse(Integer.MAX_VALUE);
        return countMap.entrySet().stream()
                .filter(entry -> entry.getValue().equals(num))
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
    }

    private static Map<Integer,Integer> getCountMap(TreeNode node, Map<Integer,Integer> countMap) {
        if (node == null) {
            return countMap;
        }
        // 左
        countMap = getCountMap(node.left, countMap);
        // 中
        countMap.put(node.element,countMap.getOrDefault(node.element,0) +1);
        // 右
        countMap = getCountMap(node.right,countMap);
        return countMap;
    }

    private static void getMode(TreeNode prev,TreeNode curr,int count,int maxCount,List<Integer> result) {
        if (curr == null) {
            return;
        }
        // 左
        getMode(prev,curr.left,count,maxCount,result);
        // 叶子节点
        if (prev == null) {
            count = 1;
        }else if (prev.element == curr.element) {
            count++;
        } else {
            count=1;
        }
        // 如果当前值与最大的count相等 加入到结果集
        if (count == maxCount) {
            result.add(curr.element);
        }
        // 如果当前值比最大count大，更新maxCount，清空结果集，加入当前节点
        if (count > maxCount) {
            maxCount = count;
            result.clear();
            result.add(curr.element);
        }
        prev = curr;
        // 右
        getMode(prev,curr.right,count,maxCount,result);
    }
}
